1. Field of the Invention
The invention relates to creating a set in post-order organization from a set originally in pre-order organization. More specifically, the invention relates to generating a post-order organization of the result set of an MDX query that is in pre-order organization.
2. Description of the Related Art
Online analytical processing (OLAP) is a valuable resource for interpreting and understanding raw data in new and meaningful ways. OLAP also allows this data to be accessed in a more efficient manner and is a valuable resource in business intelligence.
OLAPs generally store data in data cubes, which are specified as a set of dimensions such as time, customer, and product. Each dimension can be further divided into a set of ordered levels. For example, the time dimension may include levels for years, and each level includes dimension members such as 2004, 2005, 2006, 2007, and 2008. These dimension members may be further organized hierarchically within the dimension; thus, the year 2004 has four children (quarters 1 through 4) and each child may have further children (for example, quarter 1 has children January, February, and March).
The MDX query language has become a standard for query language in the OLAP environment, and is used for multiple OLAP APIs, including OLE DB for OLAP, XML for Analysis, and ADOMD.NET. MDX allows a user to access information in the data cubes, much like SQL allows access to information in relational tables. For example, an MDX query may specify:
Select [Time].members on columns,   [Measures].members on rows,From [SalesCube]Where [Product].[Food]This query returns a two dimensional result set with a full list of members along the x-axis and a full list of measures associated with the cube along the y-axis. The data represented in the result set specifies the combination of time and measure members on the axes as specified. For example, the result set may read:
20066Q16Q26Q36Q420077Q17Q27Q37Q4Sales500100100100200600200100100200Qty102233204466Profit1001020304020040505060
The results shown above are listed in pre-order, meaning that the dimension member will appear in the resulting ordered list before any of its descendants. Thus, 2006 appears before its children, the quarters 6Q1, 6Q2, 6Q3, and 6Q4. If additional granularity were presented (say, at the month level), the pre-order list would specify: 2006, 6Q1, January, February, March, 6Q2, April, May, June, etc. . . .
The MDX query language supports a function named “hierarchize.” The hierarchize function places members of the dimension into hierarchical order in a pre-order format. The hierarchize function receives as a parameter a relevant set of data from the data cube, and puts members of that set into pre-order form as shown in the table above.
However, many users require data to be presented in post-order hierarchize form. Post-order hierarchize form means that the dimension member will appear in the resulting list or set after all of its descendants. Thus, the list: 6Q 1, 6Q2, 6Q3, 6Q4, 2006, 7Q1, 7Q2, 7Q3, 7Q4, 2007, is in post-order form where 6Q1 represents the first quarter of 2006, 6Q2 represents the second quarter, and so on. Again, if the granularity were at the month level, the list or set would be ordered: January, February, March, 6Q1, April, May, June, 6Q2, July, August, September, 6Q3, October, November, December, 6Q4, 2006.
Since the hierarchize operation is essentially an ordering operation on members of a set, the most efficient approaches (whether pre- or post-order) are order (n log n), where n is the number of members in the set to be ordered. Accordingly, a need exists for generating a post-order list or set of members from a pre-ordered set that preserves the (n log n) order. Ideally, such a solution does not require the storage of additional information such as identifiers to facilitate the post-order arrangement of members.